package pro.softzhang.algo.lc100;

import java.util.*;

public class LC128_LongestConsecutiveSequence {
    public static void main(String[] args) {

    }

    static class Solution {
        public int longestConsecutive(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num);
            }

            int longest = 0;
            while (!set.isEmpty()) {
                Iterator<Integer> iterator = set.iterator();
                longest = Math.max(longest, bfs(set, iterator.next()));
            }

            return longest;
        }

        private int bfs(Set<Integer> set, Integer next) {
            Queue<Integer> q = new LinkedList<>();
            q.offer(next);
            set.remove(next);

            int length = 1;
            while (!q.isEmpty()) {
                int i = q.poll();
                int[] neighbors = new int[]{i - 1, i + 1};
                for (int neighbor : neighbors) {
                    if (set.contains(neighbor)) {
                        q.offer(neighbor);
                        set.remove(neighbor);
                        length++;
                    }
                }
            }
            return length;
        }
    }
}
